/**
 * 二叉树的diff算法
 */
class TreeNode {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

const a1 = new TreeNode("A");
const b1 = new TreeNode("B");
const c1 = new TreeNode("C");
const d1 = new TreeNode("D");
const e1 = new TreeNode("E");
const f1 = new TreeNode("F");
const g1 = new TreeNode("G");
a1.left = b1;
a1.right = c1;
b1.left = d1;
b1.right = e1;
c1.left = f1;
c1.right = g1;

const a2 = JSON.parse(JSON.stringify(a1));
const h2 = new TreeNode("H");
const i2 = new TreeNode("I");
a2.left.left.left = h2;
a2.left.right = null;
a2.right.left = i2;

/**
 *      a1              a2
 *      A               A
 *    /   \           /   \
 *   B     C         B     C
 *  / \   / \       /     / \
 * D   E F   G     D     I   G
 *                /
 *               H
 */

/**
 * diff二叉树
 * @param root1 第一个二叉树
 * @param root2 第二个二叉树
 * @returns {boolean|*}
 */
function diffTree(root1, root2, diff = []) {
  if (root1 == root2) return diff;
  if (root1 == null && root2 != null) {
    diff.push({type: '新增', origin: null, now: root2});
  } else if (root1 != null && root2 == null) {
    diff.push({type: '删除', origin: root1, now: null});
  } else if (root1?.val !== root2?.val) {
    diff.push({type: '修改', origin: root1, now: root2});
    // 修改节点也要递归比较左右子树, 因为修改节点并不一定改变左右子树
    diffTree(root1?.left, root2?.left, diff);
    diffTree(root1?.right, root2?.right, diff);
  } else {
    diffTree(root1?.left, root2?.left, diff);
    diffTree(root1?.right, root2?.right, diff);
  }
  return diff;
}

console.log(diffTree(a1, a2));
